#include "editDistance.h"

editDistance::editDistance(std::string &lhs)
:_lhs(lhs)
{

}

editDistance::~editDistance()
{

}

std::size_t editDistance::nBytesCode(const char &ch)
{
    if(ch&(1<<7))
    {
        int nBytes=1;
        for(int idx=0;idx!=6;++idx)
        {
            if(ch&(1<<(6-idx)))
            {
                ++nBytes;
            }else{
                break;
            }
        }
    }
    return 1;
} 

std::size_t editDistance::strngLength(const std::string &str)
{
    std::size_t len=0;
    for(std::size_t idx=0;idx!=str.size();++idx)
    {
        int nBytes=nBytesCode(str[idx]);
        idx+=(nBytes-1);
        ++len;
    }
    return len;
}

int editDistance::triple_min(const int &a,const int &b,const int &c)
{
    return a<b?(a<c?a:c):(b<c?b:c);
}

int editDistance::distanceEdit(const std::string &rhs)
{
    size_t lhs_len=strngLength(_lhs);
    size_t rhs_len=strngLength(rhs);
    int distance[lhs_len + 1][rhs_len + 1];
    
    for(size_t idx=0;idx<=lhs_len;++idx)
    {
       distance[idx][0]=idx; 
    }
    for(size_t idx=0;idx<=rhs_len;++idx)
    {
        distance[0][idx]=idx;
    }

    std::string sublhs,subrhs;
    for(std::size_t i=1,lhs_idx=0;i<=lhs_len;++i,++lhs_idx)
    {
        size_t nBytes=nBytesCode(_lhs[lhs_idx]);
        sublhs=_lhs.substr(lhs_idx,nBytes);
        lhs_idx+=(nBytes-1);

        for(std::size_t j=1,rhs_idx=0;j<=rhs_len;++j,++rhs_idx)
        {   
            nBytes=nBytesCode(rhs[rhs_idx]);
            subrhs=rhs.substr(rhs_idx,nBytes);
            rhs_idx+=(nBytes-1);

            if(sublhs==subrhs)
            {
                distance[i][j]=distance[i-1][j-1];
            }else{
                distance[i][j]=triple_min(distance[i-1][j]+1,
                                          distance[i][j-1]+1,
                                          distance[i-1][j-1]+1);
            }
        }
    }
    return distance[lhs_len][rhs_len];
}

